package interviewClassic150;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        //定义一个字符串数组，用于映射strs，格式为a1b0...
        int n = strs.length;
        String[] keys = new String[n];
        //每个字母出现次数的map
        int[] map = new int[26];
        StringBuilder sb = new StringBuilder();//用于组装字符串
        //遍历strs
        for (int i = 0; i < n; i++) {
            String curStr = strs[i];
            //遍历当前字符串每个字符出现次数
            int curLen = curStr.length();
            for (int j = 0; j < curLen; j++) {
                char curCh = curStr.charAt(j);
                int index = curCh - 'a';
                map[index]++;
            }
            //计算当前字符串的字符分别出现次数，将其组装成字符串
            for (int j = 0; j < 26; j++) {
                //组装字母
                sb.append((char)('a' + j));
                sb.append(map[j]);//组装出现次数
                //组装后将map对应位置置零
                map[j] = 0;
            }
            //将对应字符串放入keys
            keys[i] = sb.toString();
            //清空sb
            sb.delete(0,sb.length());
        }

        //每一个字符串对应一个key，利用Map<String,List<String>>组装起来
        Map<String,List<String>> KV = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String curKey = keys[i];
            String curValue = strs[i];
            List<String> curList = KV.getOrDefault(curKey, new ArrayList<>());
            curList.add(curValue);
            KV.put(curKey,curList);
        }
        //转换成List<List<String>>
        List<List<String>> res = new ArrayList<>(KV.values());
        return res;
    }
}
